/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/next-permutation
   @Language: C++
   @Datetime: 19-06-03 14:04
   */

// Method 1, std
class Solution {
public:
	void nextPermutation(vector<int>& nums) {
		next_permutation(nums.begin(),nums.end());
	}
};

// Method 2, implement
class Solution {
public:
	void nextPermutation(vector<int>& nums) {
		int i=0, j=nums.size()-1;
		for(i=nums.size()-1; i && nums[i-1]>=nums[i]; --i);
		if(i){
			for(j=nums.size()-1; i<j && nums[i-1]>=nums[j]; --j);
			swap(nums[i-1],nums[j]);
		}
		reverse(nums.begin()+(i-1==j?0:i),nums.end());
	}
};
